package com.company;

import java.util.ArrayList;

/**
 * @author zhf
 * @date 2021/10/19
 */
/*
合并K个升序链表

使用分治法合并K个单链表
 */
public class KList {


    /*
    主函数
     */
    public static void main(String[] args) {

    }

    /*
    创建链表数组
     */
    public ListNode[] List(ListNode single){
//        ListNode[] data = new ListNode[];
        KList List1 = new KList();
        List1.addNode(1);
        List1.addNode(4);
        List1.addNode(5);

        KList List2 = new KList();
        List1.addNode(1);
        List1.addNode(3);
        List1.addNode(4);

        KList List3 = new KList();
        List1.addNode(2);
        List1.addNode(6);



        return null;
    }
    /*
    头插法创建单链表
     */
    public void addNode(int data){
        ListNode first = new ListNode();
        ListNode s = new ListNode(data);
        s.next = first.next;
        first.next = s;
    }

    /*
    定义单链表；
     */
    public class ListNode{
        int val;
        ListNode next;
        ListNode(){};
        ListNode(int val){this.val = val;}
        ListNode(int val, ListNode next){
            this.val = val;
            this.next = next;
        }

    }

    //合并K个单链表
    public ListNode mergeKLists(ListNode[] lists) {
       return merge(lists, 0, lists.length-1);
    }

    //分治法、递归；
    /*
    分治法，每次讲链表组中的链表两两合并；
     */
    public ListNode merge(ListNode[] lists,int left,int right){
        if (left == right){
            return lists[left];
        }
        if (left > right){
            return null;
        }

        //每次获得中间的链表；
        int mid = (left+right)/2;

        return mergeTwoLists(merge(lists,left,mid),merge(lists,mid+1,right));
    }

    //合并两条单链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode pre = head;
        if (l1 == null){
            return l2;
        }
        if (l2 == null){
            return l1;
        }
        while (l1!=null&&l2!=null){
            if (l1.val <= l2.val){
                pre.next = l1;
                l1 = l1.next;
            }
            else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        if (l1 == null){
            pre.next = l2;
        }
        if (l2 == null){
            pre.next = l1;
        }
        return head.next;
    }
}
